/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/maximum-product-subarray
@Language: C++
@Datetime: 16-02-09 08:17
*/

class Solution {
    int getmax(int a,int b,int c){
        a = (a>b?a:b);
        a = (a>c?a:c);
        return a;
    }
    int getmin(int a,int b,int c){
        a=(a<b?a:b);
        a=(a<c?a:c);
        return a;
    }
public:
    /**
     * @param nums: a vector of integers
     * @return: an integer
     */
    int maxProduct(vector<int>& nums) {
        // write your code here
        int maxpro;
        vector<int> maxs,mins;
        if(nums.size()==0)
            return 0;
        maxs.push_back(nums[0]);
        mins.push_back(nums[0]);
        maxpro=nums[0];
        
        for(int i=1;i<nums.size();++i){
            maxs.push_back(getmax(nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]));
            mins.push_back(getmin(nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]));
            maxpro=(maxpro>maxs[i]?maxpro:maxs[i]);
        }
        return maxpro;
    }
};